//
// Created by francklinson on 2021/5/25.
//
/*

给你一个数组nums，对于其中每个元素nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个nums[i]你必须计算出有效的j的数量，其中 j 满足j != i 且 nums[j] < nums[i]。

以数组形式返回答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int> &nums) { // 计数排序
        vector<int> cnt(101, 0);
        int n = (int) nums.size();
        for (int i = 0; i < n; i++) {
            cnt[nums[i]]++;
        }
        for (int i = 1; i <= 100; i++) {
            cnt[i] += cnt[i - 1];
        }
        vector<int> ret;
        ret.reserve(n);
        for (int i = 0; i < n; i++) {
            ret.push_back(nums[i] == 0 ? 0 : cnt[nums[i] - 1]);
        }
        return ret;

    }

    vector<int> smallerNumbersThanCurrent2(vector<int> &nums) { // 排序
        vector<pair<int, int>> data;
        int n = (int) nums.size();
        for (int i = 0; i < n; i++) {
            data.emplace_back(nums[i], i);
        }
        sort(data.begin(), data.end());

        vector<int> ret(n, 0);
        int prev = -1;
        for (int i = 0; i < n; i++) {
            if (prev == -1 || data[i].first != data[i - 1].first) {
                prev = i;
            }
            ret[data[i].second] = prev;
        }
        return ret;

    }

};

int main() {
    vector<int> v{8, 1, 2, 2, 3};
    Solution sol;
    auto ans = sol.smallerNumbersThanCurrent(v);
    for (auto &x:ans) cout << x << endl;
    return 0;
}
